package query

// https://leetcode.cn/problems/search-in-rotated-sorted-array/ leetcode-33
func search(nums []int, target int) int {
	low, high := 0, len(nums)-1
	mid := getIntMid(low, high)

	for low <= high {
		if nums[mid] == target {
			return mid
		}

		if nums[low] == target {
			return low
		}

		if nums[high] == target {
			return high
		}

		if nums[mid] < target {
			if nums[low] > nums[mid] && nums[high] > nums[mid] && nums[low] < target {
				high = mid - 1
			} else {
				low = mid + 1
			}
		} else {
			if nums[low] < nums[mid] && nums[high] < nums[mid] && target < nums[low] {
				low = mid + 1
			} else {
				high = mid - 1
			}
		}
		mid = getIntMid(low, high)
	}
	return -1
}

func getIntMid(low, high int) int {
	return low + (high-low)>>1
}
